﻿using System;

namespace SortAndDatastruct {
    /// <summary>
    /// 快速排序算法[不需要额外空间]
    /// </summary>
    class QuickSort : ISort {
        /// <summary>
        /// 分治思想的核心算法
        /// 将array数组分成以基准对象为界的2个子数组
        /// 使得基准对象之前的比他小，之后的比他大
        /// 该基准对象一般选用数组的最后一个元素
        /// </summary>
        /// <param name="Array">待排序的数组</param>
        /// <param name="Left">带排序的左端</param>
        /// <param name="Right">待排序的右端</param>
        /// <returns>返回选中的基准对象的索引</returns>
        int Partition(ref int[] Array, int Left, int Right) {
            int x = Array[Right];
            int index = Left - 1;
            for (int i = Left; i < Right; ++i) {
                if (Array[i] <= x) {
                    SortHelper.SWAP(ref Array[++index], ref Array[i]);
                }
            }
            //这一步可以并入上个循环
            //但思路没这样表达清晰：在比较完后，将基准对象调入数组中间
            SortHelper.SWAP(ref Array[++index], ref Array[Right]);
            return index;
        }
        /// <summary>
        /// 快速排序的随机化版本
        /// 值得注意的是（容易出错），产生随机数的边界需要和参数一致，而不能写死（比如0，length）。
        /// 这种版本的期望性能是：O(nlgn).
        /// </summary>
        /// <param name="Array">待排序的数组</param>
        /// <param name="Left">数组的左端索引</param>
        /// <param name="Right">数组的右端索引</param>
        /// <returns>返回基准对象的索引</returns>
        int RandomPartition(ref int[] Array, int Left, int Right) {
            Random random = new Random();
            SortHelper.SWAP(ref Array[random.Next(Left, Right)], ref Array[Right]);
            return Partition(ref Array, Left, Right);
        }

        /// <summary>
        /// 快速排序算法
        /// </summary>
        /// <param name="Array">待排序的数组</param>
        /// <param name="Left">待排序的数组的左端</param>
        /// <param name="Right">待排序的数组的右端</param>
        void Sort(ref int[] Array, int Left, int Right) {
            if (Array == null || Array.Length < 2 
                 || Right >= Array.Length || Left < 0) return;
            if (Left < Right) {
                int q = RandomPartition(ref Array, Left, Right);//也可以直接用Partition();
                if (q == -1) return;
                Sort(ref Array, Left, q - 1);
                Sort(ref Array, q + 1, Right);
            }
        }

        /// <summary>
        /// 排序接口
        /// </summary>
        /// <param name="Array">待排序的数组</param>
        internal override void Sort(ref int[] Array) {
            Sort(ref Array, 0, Array.Length - 1);
        }

    }
}
